import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.Scanner;
import java.util.SplittableRandom;
import java.util.Stack;

public class Solution {
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        TreeNode(int val){
            this.val = val;
        }
    }
    public static void inOrder(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> s = new Stack<>();
        while(true){
            while(root!=null){
                s.add(root);
                root = root.left;
            }
            if(s.empty())break;
            root = s.pop();
            System.out.println(root.val);
            root = root.right;
        }
    }
    public static void preOrder(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> s =new Stack<>();
        while(true){
            while(root!=null){
                System.out.println(root.val);
                s.add(root);
                root = root.left;
            }
            if(s.empty())break;
            root = s.pop();
            root = root.right;
        }
    }
    public static void postOrder(TreeNode root){
        if(root==null) return;
        TreeNode lastVisit = new TreeNode(-1);
        Stack<TreeNode> s = new Stack<>();
        while(root!=null){
            s.add(root);
            root = root.left;
        }
        while(!s.empty()){
            root = s.peek();
            if(root.right==null||root.right==lastVisit){
                root = s.pop();
                System.out.println(root.val);
                lastVisit = root;
            }else{
                root = root.right;
                while(root!=null){
                    s.add(root);
                    root = root.left;
                }
            }
        }
    }
    public static void main(String args[]){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node7;
        node3.right = node8;
//        inOrder(node1);
//        preOrder(node1);
        postOrder(node1);
        System.out.println();

    }

}

